package HashMap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 *  题目 ：变位词组
 *  题目详述 ：
 *  给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
 *  注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
 */
public class OfferP33 {
    /**
     * 核心思想 ：
     * 方法一 （使用哈希表，key存储排序后的字符串，通过排序后的字符串进行变位词的区别） ：
     *     即，哈希表的key存储的是String（每个字符串若是变位词的话，其字符串进行排序后，所返回的结果必然是相同的字符串）
     * 思考：如何对于字符串进项排序？（由于两个字节即能够表示所有的字符，即此方法适用于所有字符进行排序）
     *     （1）将字符串转化为字符数组；
     *     （2）根据ASCII码值，对于字符数组进行排序
     *     （3）再次将字符数组转化为字符串；
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 可以将字符串转化为字符数组，再对于字符数组进行排序
            // （若是变位词的话，排序后的字符数组必然是一致的；一样的）
            /**
             *  问题 ：？？？
             *  若是两个一模一样的字符串，其不为变位词，但是此排序结果所将其归类为变位词
             */
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
//            String sorted = new String(chars);
            String sorted = Arrays.toString(chars);

//            String sorted = chars.toString();
            // 若是使用tostring方法的话,所获得的字符串虽然值相同，但是其指向的不是同一个字符串
            // （为保证其key一致的话，需要使得字符串值相同的，指向hashmap中同一个key）
//            System.out.println(sorted);
            // 若是hashmap中不存在此键值对的话，即向其中插入一个键值对（key = sorted，value = 新建的链表）
            map.putIfAbsent(sorted,new ArrayList<String>());
            // 向hashmap的value中的链表中插入此字符串
            map.get(sorted).add(str);
        }
        // 需要的返回值 ：List<List<String>>
        return new ArrayList<>(map.values());
    }
}
